Search results for "Average-case complexity"
showing 7 items of 7 documents
A NEW COMPLEXITY FUNCTION FOR WORDS BASED ON PERIODICITY
2013
Motivated by the extension of the critical factorization theorem to infinite words, we study the (local) periodicity function, i.e. the function that, for any position in a word, gives the size of the shortest square centered in that position. We prove that this function characterizes any binary word up to exchange of letters. We then introduce a new complexity function for words (the periodicity complexity) that, for any position in the word, gives the average value of the periodicity function up to that position. The new complexity function is independent from the other commonly used complexity measures as, for instance, the factor complexity. Indeed, whereas any infinite word with bound…
Algorithmic Information Theory and Computational Complexity
2013
We present examples where theorems on complexity of computation are proved using methods in algorithmic information theory. The first example is a non-effective construction of a language for which the size of any deterministic finite automaton exceeds the size of a probabilistic finite automaton with a bounded error exponentially. The second example refers to frequency computation. Frequency computation was introduced by Rose and McNaughton in early sixties and developed by Trakhtenbrot, Kinber, Degtev, Wechsung, Hinrichs and others. A transducer is a finite-state automaton with an input and an output. We consider the possibilities of probabilistic and frequency transducers and prove sever…
Non-intersecting Complexity
2006
A new complexity measure for Boolean functions is introduced in this article. It has a link to the query algorithms: it stands between both polynomial degree and non-deterministic complexity on one hand and still is a lower bound for deterministic complexity. Some inequalities and counterexamples are presented and usage in symmetrisation polynomials is considered.
Effects of Kolmogorov complexity present in inductive inference as well
1997
For all complexity measures in Kolmogorov complexity the effect discovered by P. Martin-Lof holds. For every infinite binary sequence there is a wide gap between the supremum and the infimum of the complexity of initial fragments of the sequence. It is assumed that that this inevitable gap is characteristic of Kolmogorov complexity, and it is caused by the highly abstract nature of the unrestricted Kolmogorov complexity.
Learning-Graph-Based Quantum Algorithm for k-distinctness
2012
We present a quantum algorithm solving the $k$-distinctness problem in $O(n^{1-2^{k-2}/(2^k-1)})$ queries with a bounded error. This improves the previous $O(n^{k/(k+1)})$-query algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee arXiv:1108.3022, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler. Additionally, we introduce an $O(\sqrt{n}\alpha^{1/6})$ algorithm for the graph collision problem where $\alpha$ is the independence number of the graph.
Transition Function Complexity of Finite Automata
2011
State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. In this paper we consider a new measure of descriptional complexity of finite automata -- BC-complexity. Comparison of it with the state complexity is carried out here as well as some interesting minimization properties are discussed. It is shown that minimization of the number of states can lead to a superpolynomial increase of BC-complexity.
Inductive inference of recursive functions: Complexity bounds
2005
This survey includes principal results on complexity of inductive inference for recursively enumerable classes of total recursive functions. Inductive inference is a process to find an algorithm from sample computations. In the case when the given class of functions is recursively enumerable it is easy to define a natural complexity measure for the inductive inference, namely, the worst-case mindchange number for the first n functions in the given class. Surely, the complexity depends not only on the class, but also on the numbering, i.e. which function is the first, which one is the second, etc. It turns out that, if the result of inference is Goedel number, then complexity of inference ma…